import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public void levelOrder(TreeNode root) {
        if(root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int size = queue.size();

            while(size != 0) {
                TreeNode tmp = queue.poll();
                System.out.print(tmp.val + " ");
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }
                size--;
            }
        }
    }

    public int getNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int count = 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            count += size;
            while(size != 0) {
                TreeNode tmp = queue.poll();
                System.out.print(tmp.val + " ");
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }
                size--;
            }
        }

        return count;
    }

    public int getNodesNor(TreeNode root){
        if(root == null) {
            return 0;
        }

        return getNodesNor(root.left) + getNodesNor(root.right) + 1;
    }

    public int getLeavesNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }

        if(root.left == null && root.right == null) {
            return 1;
        }

        return getLeavesNodes(root.left) + getLeavesNodes(root.right);
    }

    public int getLeavesNodesNor(TreeNode root) {
        if(root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();

            while(size != 0) {
                TreeNode tmp = queue.poll();
                System.out.print(tmp.val + " ");
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }
                if(tmp.left == null && tmp.right == null) {
                    count += 1;
                }
                size--;
            }
        }
        return count;
    }

    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);

        return Math.max(leftH, rightH) + 1;
    }

    public int getHeightNor(TreeNode root) {
        if(root == null) {
            return 0;
        }

        //层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int height = 0;

        while(!queue.isEmpty()) {
            int size = queue.size();
            height++;
            while(size != 0) {
                TreeNode tmp = queue.poll();
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }

                size--;
            }
        }

        return height;
    }

    public int getKNodes(TreeNode root, int k) {
        if(root == null) {
            return 0;
        }

        if(k == 1) {
            return 1;
        }

        return getKNodes(root.left,k-1) + getKNodes(root.right,k-1);
    }

    public boolean isCompleteTree(TreeNode root) {
        if(root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        //将所有的结点入队列包括空节点
        while(!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if(tmp != null) {
                queue.offer(root.left);
                queue.offer(root.right);
            } else {
                break;
            }
        }

        while(!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if(tmp != null) {
                return false;
            }
        }
        return true;
    }
}
